#pragma once

#include <cstring>
#include <iterator>
#include <stdexcept>
#include <string>
#include <iostream>
#include <algorithm>
#include <vector>
#include <assert.h>
#include <type_traits>

namespace good_cptl
{

template <class Iter>
class Range
{
private:
  using iter_traits = std::iterator_traits<Iter>;
public:
  using value_type = typename iter_traits::value_type;
  using size_type = std::size_t;
  using difference_type = typename iter_traits::difference_type;
  using iterator = Iter;
  using const_iterator = Iter;
  using reference = typename iter_traits::reference;
  using const_reference = std::conditional<
      std::is_lvalue_reference_v<reference>,
      std::add_lvalue_reference_t<
          std::add_const_t<std::remove_reference_t<reference>>>,
      std::conditional<
          std::is_rvalue_reference_v<reference>,
          std::add_rvalue_reference_t<
              std::add_const_t<std::remove_reference_t<reference>>>,
          reference>>;
  //using const_reference = typename iter_traits::const_reference;

  using const_range_type = typename std::conditional<std::is_same<Iter, char*>::value
                                                  || std::is_same<Iter, unsigned char*>::value,
                                                  Range<const value_type*>, Range<Iter>>::type;

  constexpr Range(Iter start, Iter end) : b_(start), e_(end) {}
  constexpr Range(Iter start, size_t size) : b_(start), e_(start + size) {}
  Range(std::nullptr_t) = delete;

  void clear() {
    b_ = Iter();
    e_ = Iter();
  }

  void assign(Iter start, Iter end) {
    b_ = start;
    e_ = end;
  }

  void reset(Iter start, size_type size) {
    b_ = start;
    e_ = start + size;
  }

  constexpr size_type size() const {
    return size_type(e_ - b_);
  }

  constexpr size_type walk_size() const {
    return size_type(std::distance(b_, e_));
  }

  constexpr bool empty() const { return b_ == e_; }
  constexpr Iter data() const { return b_; }
  constexpr Iter start() const { return b_; }
  constexpr Iter begin() const { return b_; }
  constexpr Iter end() const { return e_; }
  constexpr Iter cbegin() const { return b_; }
  constexpr Iter cend() const { return e_; }
  reference front() {
    return *b_;
  }
  reference back() {
    return *std::prev(e_);
  }
  const_reference front() const {
    return *b_;
  }
  const_reference back() const {
    return *std::prev(e_);
  }

  reference operator[](size_t i) {
    assert(i < size());
    return b_[i];
  }

  const_reference operator[](size_t i) const {
    assert(i < size());
    return b_[i];
  }

  reference at(size_t i) {
    assert(i < size());
    return b_[i];
  }

  const_reference at(size_t i) const {
    assert(i < size());
    return b_[i];
  }

  void advance(size_type n) {
    assert(n <= size());
    b_ += n;
  }

  void subtract(size_type n) {
    assert(n <= size());
    e_ -= n;
  }
  void pop_front() {
    assert(b_ < e_);
    ++b_;
  }

  void pop_back() {
    assert(b_ < e_);
    --e_;
  }

  size_type find(const_range_type str) const {
    return boyer_moore_find(cast_to_const(), str);
  }

  size_type find(const value_type& c) const {
    return std_find(cast_to_const(), c);
  }

  size_type rfind(const value_type& c) const {
    return rfind(cast_to_const(), c);
  }
private:
  const_range_type cast_to_const() const { return const_range_type(*this); }
  Range subpiece(size_type first, size_type length) const {
    if (first > size()) {
      throw std::out_of_range("index out of range");
    }
    return Range(b_ + first, std::min(length, size() - first));
  }



private:
  Iter b_;
  Iter e_;
};

template<
    class Iter,
    class Comp = std::equal_to<typename Range<Iter>::value_type>>
size_t boyer_moore_find(
    const Range<Iter>& haystack,
    const Range<Iter>& needle,
    Comp eq = Comp());

template <class Iter, class Comp>
size_t boyer_moore_find(const Range<Iter>& haystack, const Range<Iter>& needle, Comp eq)
{
  auto const nsize = needle.size();
  if (haystack.size() < nsize) {
    return std::string::npos;
  }
  if (nsize == 0) {
    return 0;
  }
  auto const nsize_1 = nsize - 1;
  auto const last_needle = needle[nsize_1];
  size_t skip = 0;

  auto beg = haystack.begin();
  auto end = haystack.end() - nsize_1;

  while (beg < end) {
    while (!eq(beg[nsize_1], last_needle)) {
      if (++beg == end) {
        return std::string::npos;
      }
    }
    for (size_t j = 0;;) {
      if (!eq(beg[j], needle[j])) {
        if (skip == 0) {
          skip = 1;
          while (skip <= nsize_1 && !eq(needle[nsize_1 - skip], last_needle)) {
            ++skip;
          }
        }
        beg += skip;
        break;
      }
      if (++j == nsize) {
        return size_t(beg - haystack.begin());
      }
    }
  }
  return std::string::npos;
}



template <class Iter>
size_t std_find(const Range<Iter>& haystack,
                const typename Range<Iter>::value_type& needle) {
  auto pos = std::find(haystack.begin(), haystack.end(), needle);
  return pos == haystack.end()? std::string::npos : size_t(pos - haystack.begin());
}

template <class Iter>
size_t rfind(const Range<Iter>& haystack,
             const typename Range<Iter>::value_type& needle) {
  for (auto i = haystack.size(); i-- > 0;) {
    if (haystack[i] == needle) {
      return i;
    }
  }
  return std::string::npos;
}

template <>
inline size_t std_find(const Range<const char*>& haystack, const char& needle) {
  if (haystack.empty()) {
    return std::string::npos;
  }
  auto pos = static_cast<const unsigned char*>(
      ::memchr(haystack.data(), needle, haystack.size()));
  return pos == nullptr ? std::string::npos : pos - haystack.data();
}

template <>
inline size_t rfind(const Range<const char*>& haystack, const char& needle) {
  if (haystack.empty()) {
    return std::string::npos;
  }
  auto pos = static_cast<const unsigned char*>(
      memrchr(haystack.data(), needle, haystack.size()));
  return pos == nullptr ? std::string::npos : pos - haystack.data();
}


class StringPieceLite
{
public:
  StringPieceLite(const char* b, const char* e) : b_(b), e_(e) {}
  const char* data() const { return b_; }
  const char* begin() const { return b_; }
  const char* end() const { return e_; }
  size_t size() const { return size_t(e_ - b_); }
  bool empty() const { return size() == 0; }
  const char& operator[](size_t i) const {
    return b_[i];
  }
  template <typename Range>
  explicit operator Range() const {
    return Range(begin(), end());
  }
private:
  const char* b_;
  const char* e_;
};

inline size_t qfind_first_byte_of_std();


}




